//计数排序
/*
最大和最小值
确认临时桶的大小--------最大值-最小值
下标即为数组中的数并统计出现的次数
然后遍历该桶并覆盖掉原来的无规则数组
*/

//计数排序 平均时间复杂度O(N+K),空间复杂度O(N),稳定
void Sorts::count(vector<int>& nums)
{
    if (nums.size() <= 1)
        return;
    auto minmax = std::minmax_element(nums.begin(), nums.end()); // minmax_element(begin，end)可以输入迭代器而minmax(l,r)不能输入迭代器
    int min = *minmax.first;
    int max = *minmax.second;
    int index = 0;
    vector<int> sortArr(max - min + 1, 0); // 创建一段数组用来存储每个元素个数
    vector<int> result(nums.size()); // 创建一段数组用来存储每个元素个数
    for (const auto& it : nums) // 遍历原始数组，计算所有元素个数；sortArr下标是元素，值是该元素个数
    {
        sortArr[it - min]++;
    }
    for (int i = 0; i < sortArr.size(); ++i) // 遍历有序数组，值为非零则取出排列
    {
        while (sortArr[i])
        {
            result[index] = i + min;
            ++index;
            --sortArr[i];
        }
    }
    nums = result;
}

